package leetcode.year2021.month11;

import java.util.HashMap;
import java.util.Map;

// 337. 打家劫舍 III
public class _17_2Rob337 {
  // 后序遍历+动态规划，使用map存储
  // 使用后序遍历，先遍历前两个节点，使用 f(o)表示包含当前节点的情况下的最大值，使用g(o)表示不包含当前节点的情况下的最大值
  // 那么可以得出f(o) = g(l) + g(r) + root.val
  // 那么可以得出g(o) = Math.max(f(l),g(l)) + Math.max(f(r),g(r))
  Map<TreeNode, Integer> f = new HashMap<>();
  Map<TreeNode, Integer> g = new HashMap<>();

  public int rob(TreeNode root) {
    if (root == null) {
      return 0;
    }

    rob(root.right);
    rob(root.left);

    f.put(root, g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0) + root.val);
    g.put(root, Math.max(f.getOrDefault(root.left, 0), g.getOrDefault(root.left, 0)) +
            Math.max(f.getOrDefault(root.right, 0), g.getOrDefault(root.right, 0)));

    return Math.max(f.get(root), g.get(root));
  }
//  // 递归解法，我觉得没问题的啦，但是报超时了，呜呜呜
//  public int rob(TreeNode root) {
//    if (root == null) {
//      return 0;
//    }
//    int ansHaveCurrNode = root.val;
//    int ansHaveNotCurrNode = 0;
//    if (root.left != null) {
//      ansHaveNotCurrNode += rob(root.left);
//      ansHaveCurrNode += rob(root.left.left);
//      ansHaveCurrNode += rob(root.left.right);
//    }
//    if (root.right != null) {
//      ansHaveNotCurrNode += rob(root.right);
//      ansHaveCurrNode += rob(root.right.left);
//      ansHaveCurrNode += rob(root.right.right);
//    }
//
//    return Math.max(ansHaveCurrNode,ansHaveNotCurrNode);
//  }

  /**
   * 337. 打家劫舍 III
   * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
   * <p>
   * 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
   * <p>
   * 示例 1:
   * <p>
   * 输入: [3,2,3,null,3,null,1]
   * <p>
   * 3
   * / \
   * 2   3
   * \   \
   * 3   1
   * <p>
   * 输出: 7
   * 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
   * 示例 2:
   * <p>
   * 输入: [3,4,5,1,3,null,1]
   * <p>
   * 3
   * / \
   * 4   5
   * / \   \
   * 1   3   1
   * <p>
   * 输出: 9
   * 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
   */

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
      this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}
